Skip to main content

「0A」反悔贪心

普通的贪心算法是“鼠目寸光”的：一旦做出了当前看来最优的选择，就永远不再更改。但这种策略在复杂约束下容易陷入局部最优解。反悔贪心的核心就在于：先按照贪心策略选一个，但同时留下一个“后悔药”，如果后面发现之前的选择不是最优的，可以通过某种方式撤销并替换掉它。

反悔贪心通常分为三个步骤：

  1. 直接贪心：根据某种指标（如价格、价值）进行初步选择。
  2. 加入反悔堆：将这个选择存入一个 优先队列（堆） 中，作为未来可以被“替换”的备选项。
  3. 动态修正：当遇到后续更好的选项但受限于约束（如数量限制）时，从堆中取出最差的旧选择，将其替换为当前选择，并补齐差价。

相关题目​

Supermarket 超市

超市里有 NN 件商品，每件商品都有利润 pip_i 和过期时间 did_i ,每天只能卖一件商品，过期商品不能再卖。

求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。

考虑到过期时间早的商品需要早点售出，所以将商品按照过期时间排序，接下来，按顺序遍历排过序的每件商品。

若当前商品的过期时间为 tt，已经选择卖出的商品数量为 mm。

  • 若 t>mt > m，则有时间卖出当前商品，我们将当前商品加入待卖出的商品集合中。
  • 若 t≤mt \le m，则意味这前 tt 天，每天都有商品卖出，但是如果当前商品的利润大于待卖出商品集合中的某件商品的话，用当前商品替换掉该利润低的商品，可以获得更大的收益，当然，替换掉利润最低的商品收益更高。

为了快速的找到利润最低的商品，我们可以维护一个小根堆，用来保存待卖出商品的利润。

参考代码
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10;

int n;
pair<int, int> A[N];

int main() {
  while (cin >> n) {
    for (int i = 1; i <= n; i++) cin >> A[i].first >> A[i].second;
    sort(A + 1, A + n + 1, [](const auto &a, const auto &b) {
      return a.second < b.second;
    });

    priority_queue<int, vector<int>, greater<int> > q;
    for (int i = 1; i <= n; i++) {
      if (A[i].second > q.size()) q.push(A[i].first);
      else {
        if (A[i].first > q.top()) q.pop(), q.push(A[i].first);
      }
    }

    int ans = 0;
    while (q.size()) ans += q.top(), q.pop();
    cout << ans <<p endl;
  }
}

例2. Buy Low Sell High​

Buy Low Sell High

你手中有无限的钱，你也可以完美地预测某只股票接下来 NN 天的价格，你想利用这一知识再赚更多的钱，但你每天只想买卖一股，这表明你每天要么什么都不干，要么买入一股，要么卖出一股。起初你没有股票，你也不能在没有股票时卖出股票。你希望在第 NN 天结束时不持有股票，并最大化盈利。

一个不影响答案的处理，我们假设每天都可以买入股票，但是，要能够找到配对的两天，一天买入，一天卖出，才能获得相应的收益。

对于当前位置上的数 aia_i，假设要在当天卖出股票的话，那么会有两种情况：

  1. 选择前面买入的位置 xx，新增加的贡献为 ai−axa_i - a_x。
  2. 选择前面卖出股票的某个位置 xx，将该位置修改为买入股票，这是我们反悔的地方。因为位置 xx 不再提供收入，所以新增加的贡献依然为 ai−axa_i - a_x。

每个位置的状态可能是买入股票，或者卖出。如果一个位置由卖出转为买入，那么，该位置以后都不再会作为卖出位置出现，因为前面没有位置与其配对（买入）。

4
3 4 5 8

因此，我们维护 ii 之前的位置，要使得贡献贡献最大，使用优先队列维护最小值。若在位置 ii 卖出了股票，那么我们将位置 ii 对于的值置于优先队列，表示该位置是一个卖出股票的位置。同时，无论位置 ii 是否卖出股票，都将位置 ii 再一次放入优先队列，这是因为该位置也可能作为买入操作的位置。

参考代码
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  priority_queue<int> q;
  
  int n; cin >> n;
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    int x; cin >> x;
    if (q.size() && x > -q.top()) {
      ans += x + q.top();
      q.pop();
      q.push(-x);
    }
    q.push(-x);
  }
  cout << ans <<details endl;
}

例3. 建筑抢修​

建筑抢修

T 部落的基地里已经有 NN 个建筑设施受到了损伤。T 部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间 t1t_1。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间 t2t_2 之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。

例4. 数据备份​

数据备份